#pragma warning(disable: 4786)
#include <iostream>
#include <string>
using namespace std;
template <class T>
struct ListNode {
      ListNode *_prev;
      ListNode *_next;
      T _data;
  };
template <class T>
class myList{
//TODO
public:
	myList(){
		elem = new ListNode<T>;
		
		elem->_next = elem;
		elem->_prev = elem;
	}
	void push_back(T t);
	void sort();
	void print();
private:
	ListNode<T>* elem;
};
//TODO
template <class T>
void myList<T>::push_back(T t){
	ListNode<T>* newNode = new ListNode<T>;
	newNode->_data = t;
	newNode->_prev = elem->_prev;
	newNode->_next = elem;
	elem->_prev->_next = newNode;
	elem->_prev = newNode;
}

template <class T>
void myList<T>::sort(){
	ListNode<T>* cur = elem->_next;
	while(cur != elem){
		ListNode<T>* cur2 = cur->_next;
		while(cur2 != elem){
			if(cur->_data > cur2->_data){
				T temp = cur->_data;
				cur->_data = cur2->_data;
				cur2->_data = temp;
			}
			cur2 = cur2->_next;
		}
		cur = cur->_next;
	}
}
template <class T>
void myList<T>::print(){
	ListNode<T>* cur = elem->_next;
	while(cur != elem){
		cout << " "<<cur->_data ;
		cur = cur->_next;
	}
}

int main( )
{
   myList <int> t1;
   myList <string> t2;
   t1.push_back( 20 );
   t1.push_back( 10 );
   t1.push_back( 30 );

   cout << "Before sorting: c1 =";
   t1.print();
   cout << endl;

   t1.sort( );
   cout << "After sorting c1 =";
   t1.print();
   cout << endl;

    t2.push_back( string("Tom") );
    t2.push_back( string("Jame") );
    t2.push_back( string("Alice") );

    cout << "Before sorting: c1 =";
    t2.print();
    cout << endl;

    t2.sort( );
    cout << "After sorting c1 =";
    t2.print();
    cout << endl;

    return 0;
}
